36 队列的概念及实现(上)

队列的概念及实现

队列是一种特殊的线性表
队列仅能在线性表的两端进行操作
- 队头(Front):取出数据元素的一端
- 队尾(Rear):插入数据元素的一端
队列的特性
- 先进先出(First In First Out)
队列的操作
- 创建队列( Queue() )
- 销毁队列( ~Queue() )
- 清空队列( clear() )
- 进队列( enqueue() )
- 出队列( dequeue() )
- 获取队头元素( head() )
- 获取队列的长度( length() )
队列的实现
```
template<typename T>
class Queue : public Object
{
public:
    virtual void enqueue(const T &e) = 0;
    virtual T dequeue() = 0;
    virtual const T& head() const = 0;
    virtual const T& head() = 0;
    virtual void clear() = 0;
    virtual int length() const = 0;
};
```
队列的顺序实现
StaticQueue设计要点
- 类模板
- 使用原生数组作为队列的存储空间
- 使用模板参数决定队列的最大容量
```
template<typename T,int N>
class StaticQueue : public Queue<T>
{
public:
    StaticQueue();    //初始化成员变量
    int capacity() const;
    //...
protected:
    T m_space[N];    //队列存储空间
    int m_front;    //队头标识
    int m_rear;    //队尾标识
    int m_length;    //当前队列的长度
};
```
StaticQueue实现要点(循环计数法)
- 关键操作
  - 进队列:m_space[m_rear] = e;m_rear = (mear+1)%N;
  - 出队列:m_front = (m_front + 1)%N;
- 队列的状态
  - 队空:(m_length == 0)&&(m_front == m_rear)
  - 队满:(m_length == N)&&(m_front == m_rear)

编程实验

基于顺序存储结构的队列

#ifndef STATICQUEUE_H
#define STATICQUEUE_H

#include "Queue.h"
#include "Exception.h"

namespace KylinLib {
template<typename T,size_t N>
class StaticQueue : public Queue<T>{
public:
    virtual void enqueue(const T &value) {
        if(m_size>=N)
            THROW_EXCEPTION(InvalidParameterException,"There is no space...");
        m_space[m_rear] = value;
        m_rear = (m_rear+1)%N;
        m_size++;
    }
    virtual T dequeue() {
        if(m_size<=0)
            THROW_EXCEPTION(InvalidParameterException,"There is no element in queue...");
        auto value = head();
        m_front = (m_front+1)%N;
        m_size--;
        return value;
    }

    virtual T& head() {
        if(m_size<=0)
            THROW_EXCEPTION(InvalidParameterException,"There is no element in queue...");
        return m_space[m_front];
    }
    
    virtual const T& head() const{
        const_cast<StaticQueue*>(this)->head();
    }
    

    virtual void clear(){
        m_front = 0;
        m_rear = 0;
        m_size = 0;
    }

    virtual size_t size() const {
        return m_size;
    }

    size_t capacity() const{
        return N;
    }

private:
    T m_space[N];
    size_t m_front = 0;
  size_t m_rear = 0;
    size_t m_size = 0;
};
}
#endif // STATICQUEUE_H

小结

队列是一种特殊的线性表，具有先进先出的特性
队列只允许在线性表的两端进行操作，一端进，一端出
StaticQueue使用原生数组作为内部存储空间
StaticQueue的最大容量由模板参数决定
StaticQueue采用循环计数法提高队列操作的效率

37 队列的概念及实现(下)

队列的概念及实现(一)

讨论中......

A：这次我知道了，StaticQueue也是有缺陷的。

B：说说看，什么缺陷！

A：类似的，当数据元素为类类型，StaticQueue的对象在创建时，会多次调用元素类型的构造函数，影响效率。

B：是的，所以我们需要实现链式队列......
队列的链式存储实现
链式队列的设计要点
- 类模板，抽象父类Queue的直接子类
- 在内部使用链式结构实现元素的存储
- 只在链表的头部和尾部进行操作

编程实验(一)

基于LinkedList的队列

#ifndef LINKEDQUEUE_H
#define LINKEDQUEUE_H

#include "Queue.h"
#include "LinkedList.h"

namespace KylinLib {
template <typename T>
class LinkedQueue : public Queue<T>{
public:

    virtual void enqueue(const T &value){
    	m_list.append(value);
    }

    virtual T dequeue(){
        if(m_list.size()<=0)
            THROW_EXCEPTION(InvalidOperationException,"There is no element in the queue...");
        auto value = m_list.at(0);
        m_list.remove(0);
        return value;
    }

    virtual T& head() {
        if(m_size<=0)
            THROW_EXCEPTION(InvalidOperationException,"There is no element in the queue...");
        return m_list.at(0);
    }
    
    virtual const T& head() const{
        return const_cast<LinkedQueue*>(this)->head();
    }

    virtual void clear() {
		m_list.clear();
    }

    virtual size_t size() const {
        return m_list.size();
    }

private:
	LinkedList<T> m_list;
};
}
#endif // LINKEDQUEUE_H

队列的概念及实现(二)

问题

使用LinkedList类实现链式队列是否合适，是否有更好的方案？
队列链式存储实现的优化
链式队列的设计优化

编程实验(二)

基于Linux内核链表的队列

#ifndef LINKEDQUEUE_H
#define LINKEDQUEUE_H

#include "Queue.h"
#include "LinuxList.h"
#include "Exception.h"

namespace KylinLib {
template <typename T>
class LinkedQueue : public Queue<T>{
public:
    LinkedQueue(){
        INIT_LIST_HEAD(&m_header);
    }

    virtual void add(const T &value){
        auto node = new Node();
        if(node==nullptr)
            THROW_EXCEPTION(NoEnoughMemoryException,"There is no memory to add element...");
        node->value = value;
        list_add_tail(&node->head,&m_header);
        m_size++;
    }

    virtual void remove(){
        if(m_size<=0)
            THROW_EXCEPTION(InvalidOperationException,"There is no element in the queue...");
        auto toDel = m_header.next;
        list_del(toDel);
        m_size--;
        delete list_entry(toDel,Node,head);
    }

    virtual T& front() {
        if(m_size<=0)
            THROW_EXCEPTION(InvalidOperationException,"There is no element in the queue...");
        return list_entry(m_header.next,Node,head)->value;
    }

    virtual void clear() {
        while (m_size>0) {
            remove();
        }
    }

    virtual size_t size() const {
        return m_size;
    }

private:
    struct Node : public Object{
        list_head head;
        T value;
    };
    list_head m_header;
    size_t m_size = 0;
};
}
#endif // LINKEDQUEUE_H

小结

StaticQueue在初始化时可能多次调用元素类型的构造函数
LinkedList的组合使用能够实现队列的功能，但是不够高效
LinkedQueue的最终实现组合使用了Linux内核链表
LinkedQueue中入队和出队操作可以在常量时间内完成

队列的概念及实现​

编程实验​

小结​

37 队列的概念及实现(下)

队列的概念及实现(一)​

编程实验(一)​

队列的概念及实现(二)​

编程实验(二)​

小结​

队列的概念及实现

编程实验

小结

队列的概念及实现(一)

编程实验(一)

队列的概念及实现(二)

编程实验(二)

小结